public class MinWindow {
    public String minWindow(String s, String t) {
        // 最小覆盖子串
        // https://leetcode.cn/problems/minimum-window-substring/description/?envType=study-plan-v2&envId=top-100-liked
        // hash1用于记录t字符串中每个字符出现的次数
        int[] hash1 = new int[58];
        // hash2用于记录窗口中字符串出现的次数
        int[] hash2 = new int[58];
        // type1用于记录t字符串中出现的字符的种类
        int type1 = 0;
        // type2用于记录窗口中符合t中字符个数的字符数
        int type2 = 0;
        for (char c : t.toCharArray())
            if (hash1[c-'A']++ == 0)
                type1++;
        char[] ch = s.toCharArray();
        int minLength = 0x3f3f3f3f;
        int startIndex = -1, endIndex = -1;
        for (int left = 0, right = 0; right < ch.length; right++) {
            if (++hash2[ch[right]-'A'] == hash1[ch[right]-'A']) type2++;
            while (type1 == type2 && left <= right) {
                if (right-left+1 < minLength) {
                    minLength = right-left+1;
                    startIndex = left;
                    endIndex = right;
                }
                if (hash2[ch[left]-'A']-- == hash1[ch[left++]-'A']) type2--;
            }
        }
        return endIndex == -1 ? "" : s.substring(startIndex, endIndex+1);
    }

    public static void main(String[] args) {
        System.out.println(new MinWindow().minWindow("a", "a"));
    }
}
